package fun.ticsmyc.question;

import fun.ticsmyc.tools.ArrayTools;
import org.junit.Test;

/**
 * @author Ticsmyc
 * @date 2020-02-03 17:42
 */
public class 数组分割和荷兰国旗问题 {

    /**
     * 分割数组，小于num的放左边，大于num的放右边
     * @param arr
     * @param num
     */
    public static void divideArray(int[] arr,int num){
        ArrayTools.printArray(arr);
        int divideIndex = 0;
        for(int i=0 ; i <arr.length ; ++i){
            if(arr[i] <= num){
                ArrayTools.swap(arr, divideIndex++,i);
            }
        }
        ArrayTools.printArray(arr);
        System.out.println(divideIndex);
    }

    /**
     * 荷兰国旗， 小于num放左边，大于num放右边，等于num在中间
     * @param arr
     * @param num
     */
    public static void helanArray(int[] arr , int num){
        ArrayTools.printArray(arr);
        int headIndex = 0;
        int tailIndex = arr.length-1;

        int i =0;

        while(tailIndex != i){
            if(arr[i] <  num){
                ArrayTools.swap(arr,headIndex++,i++);
            }else if (arr[i] > num){
                ArrayTools.swap(arr,tailIndex--,i);
            }else{
                //arr[i] == num
                i++;
            }
        }
        ArrayTools.printArray(arr);
        System.out.println(headIndex+"  "+tailIndex);
    }

    @Test
    public void test(){
        int[] arr = new int[]{1,9,2,5,8,3,5,7,4,6,5,5,5};
        helanArray(arr,5);
    }

}
